// @algorithm @lc id=39 lang=cpp 
// @title combination-sum


// #define print(...)
// @test([2,3,6,7],7)=[[2,2,3],[7]]
// @test([2,3,5],8)=[[2,2,2,2],[2,3,3],[3,5]]
// @test([2],1)=[]
// @test([1],1)=[[1]]
// @test([1],2)=[[1,1]]
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> cb;
        function<void(int,vector<int>&,vector<int>::iterator)> dfs
            = [&](int sum, vector<int>& cb, vector<int>::iterator it){
            if(it == candidates.end()) return;
            if(0 == sum){
                ans.push_back(cb);
                return;
            }
            dfs(sum, cb, it+1);
            if(sum - *it >= 0){
                cb.push_back(*it);
                dfs(sum-*it, cb, it);
                cb.pop_back();
            }
        };
        dfs(target, cb, candidates.begin());
        return ans;
    }
};